Disk drives are used in many different types of computer systems to store data and include a recording medium (e.g., a magnetic recording medium or an optical recording medium) on which information can be written for storage purposes and from which stored information can be read. The recording medium is typically in the form of one or more disks that rotate about a spindle, each disk including a plurality of tracks in the form of concentric areas on which information is recorded. In a disk drive that includes multiple disks, the disks are conventionally stacked on the spindle so that corresponding tracks overlie one another. Each of the tracks is conventionally subdivided into a plurality of sectors, or segments that define the smallest amount of data that is written to or read from the disk in one operation.
Data is read from and written to the disk using a head that is positioned adjacent to the surface of the disk via an arm. In operation, the disk is rotated at a high rate of speed (e.g., 5,400 rpm, 7,200 rpm or 10,033 rpm) and the arm is pivoted by an actuator to move the head to a position above a desired track. The combination of the rotation of the disk and the movement of the head by the actuator enables the head to be positioned adjacent to any sector of the disk to access (i.e., read information from or write information to) that sector.
Disk drives may be coupled directly to a host processor to provide data storage services to the host processor. In this type of arrangement, the host processor performs basic I/O operations in connection with data requests, such as data read and write operations and the disk drive includes a controller that maintains a command queue, or list containing I/O requests, or commands issued by the host processor and waiting to be executed by the disk drive.
Disk drives also may be part of a larger data storage system comprising a plurality of disk drives and a controller, such as the Symmetrix™ system manufactured by EMC Corporation of Hopkinton, Mass. These systems may be coupled to one or more host processors and provide storage services to each host processor. In this type of arrangement, typically the host processors perform basic system I/O operations in connection with data requests, such as data read and write operations, and the controller contains one or more processors, sometimes referred to as disk directors and host directors, that control execution of I/O requests from the hosts and also initiate I/O requests themselves, for example in connection with de-staging or transferring data from the cache to the disks and in connection with administrative functions, such as data backup, mirroring, and rebuild and copy operations. The controller also contains a cache and a global memory for facilitating communication between the host processors and the disk devices. The term “data storage system” is used herein generally to refer to systems including one or more data storage devices, or disk drives providing data storage services to one or more host processors.
Disk drive performance is largely impacted by three characteristics; namely, seek time, latency and data rate. The seek time relates to the delay incurred in positioning the head above the appropriate track. In the worst case, the seek time is defined by the delay incurred in moving the head between the inner and outer tracks. The latency of the system is the time it takes for the rotation of the disk to bring the desired sector to a position underlying the head. The worst case latency is defined by the time it takes to complete a full rotation of the disk. Finally, the data rate of the system relates to how quickly data can be read from or written to the disk once the head is positioned above the appropriate sector. The data rate is dependent on the bit density of the information stored on the disk, the rate of rotation of the disk and the disk drive electronics that process the data. The seek time, latency, and data rate of a disk drive determine its data throughput (i.e., how much data can be written to or read from a disk drive within a predetermined amount of time).
In an effort to improve disk drive performance, I/O requests in the command queue are sometimes reordered, meaning that the requests are executed in an order other than the order in which they are placed in the queue. One such technique is described in a U.S. Pat. No. 5,729,718 to Au, entitled “System for Determining Lead Time Latency as Function of Head Switch, Seek, and Rotational Latencies and Utilizing Embedded Disk Drive Controller for Command Queue Reordering.”
Another approach to improving data storage system performance is to assign a priority to I/O requests. An example of this approach is described in a U.S. Pat. No. 4,425,615 to Swenson et al., entitled “Hierarchical Memory System having Cache/Disk Subsystem with Command Queues for Plural Disks.” Specifically, it is described that a priority value and a sequence number are assigned to each command as it is added to a command queue, so that the highest priority command with the lowest sequence number is executed when the disk device corresponding to the queue becomes idle.
Many times, an application requires a large amount of data to be read or written from a single location on a disk. Such I/O requests are referred to herein as “sequential I/O requests” or “contiguous I/O requests.” Because the disk drive head must move from a sector specified in a current, or presently executed I/O request to a sector specified in a next, or subsequently executed I/O request, accessing sequential or contiguous sectors is significantly faster than accessing randomly located sectors.
In response to one or more contiguous I/O requests, “prefetch algorithms” are sometimes used to copy additional data from adjacent sectors into a cache in order to speed up execution of anticipated subsequent I/O requests for the adjacent data. One such prefetch algorithm is described in a U.S. Pat. No. 6,721,870 to Yochai et al. entitled “Prefetch Algorithm for Short Sequences” and assigned to EMC Corporation of Hopkinton, Mass., the assignee of the subject application. Prefetch algorithms can also be used to take advantage of a phenomenon referred to as “locality of reference” which means that often, data required from a drive will be located adjacent to the last data read. However, although data prefetching can significantly improve system performance, if the subsequent I/O operations are directed to a random sequence of data blocks, many of which are not within the portion of data that has been staged into cache memory, then the advantage of prefetching data is considerably reduced. In fact, the performance of the system can be significantly degraded.